
/******************************************************************************************************
*******************************************************************************************************
**************************************                        *****************************************
**************************************       COMPRESSING      *****************************************
**************************************                        *****************************************
*******************************************************************************************************
******************************************************************************************************/



#include <stdio.h>
#define BITS 12                   
#define HASHING_SHIFT BITS-8     
#define MAX_VALUE (1 << BITS) - 1 
#define MAX_CODE MAX_VALUE - 1    
				  
#if BITS == 14
  #define TABLE_SIZE 18041        /* Setting the number of bits to 12, 13 or 14 */
#endif                            
#if BITS == 13                                         
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;                  /* This is the code value array        */
unsigned int *prefix_code;        /* This array holds the prefix codes   */
unsigned char *append_character;  /* This array holds the appended chars */
unsigned char decode_stack[4000]; /* This array holds the decoded string */

/**********************************************************************************
**                                                                                *
**               This program gets a file name from the command line.             *
**     It compresses the file, placing its output in a file named test.lzw.       *
**                                                                                *
**********************************************************************************/


main()
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];



  /**********************************************************************************
  *                                                                                 *
  *               The three buffers are needed for the compression phase.           *
  *                                                                                 *
  **********************************************************************************/

  code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
  prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
  append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
  if (code_value==NULL || prefix_code==NULL || append_character==NULL)
  {
    printf("Fatal error allocating table space!\n");
    exit();
  }


 
  /**********************************************************************************
  *                                                                                 *
  *          Get the file name, open it up, and open up the lzw output file         *
  *                                                                                 *
  **********************************************************************************/ 

    printf("Input file name? ");
    scanf("%s",input_file_name);

  input_file=fopen(input_file_name,"rb");
  lzw_file=fopen("test.lzw","wb");
  if (input_file==NULL || lzw_file==NULL)
  {
    printf("Fatal error opening files.\n");
    exit();
  };



  /**********************************************************************************
  *                                                                                 *
  *                                  Compress the file.                             *
  *                                                                                 *
  **********************************************************************************/ 
 

 
  compress(input_file,lzw_file);
  fclose(input_file);
  fclose(lzw_file);
  free(code_value);

}


/**********************************************************************************************
**                                                                                             *
**                              This is the compression routine.                               *
**                                                                                             *
**                                                                                             *
***********************************************************************************************/

compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;

 next_code=256;                 /** Next code is the next available string code**/
  for (i=0;i<TABLE_SIZE;i++)    /**Clear out the string table before starting**/
    code_value[i]=-1;


  i=0;
  printf("Compressing...\n");
  string_code=getc(input);    /* Get the first code */


  /*********************************************************************************************
  *                                                                                            *
  *          This is the main loop where it all happens.  This loop runs util all of           *
  *          the input has been exhausted.  Note that it stops adding codes to the             *
  *             table after all of the possible codes have been defined.                       *   
  *                                                                                            *
  **********************************************************************************************/


while ((character=getc(input)) != (unsigned)EOF)
  {
    if (++i==1000)                         /* Print a * every 1000    */
    {                                      /* input characters.   */
      i=0;                                 
      printf("*");
    }
    index=find_match(string_code,character);/* See if the string is in */
    if (code_value[index] != -1)            /* the table.  If it is,   */
      string_code=code_value[index];        /* get the code value.  If */
    else                                    /* the string is not in the*/
    {                                       /* table, try to add it.   */
      if (next_code <= MAX_CODE)
      {
	code_value[index]=next_code++;
	prefix_code[index]=string_code;
	append_character[index]=character;
      }
      output_code(output,string_code);  /* When a string is found  */
      string_code=character;            /* that is not in the table*/
    }                                   /*  output the last string*/
  }  
  printf("\n** The Compress File Is: Test.lzw **\n "); /* after adding the new one*/
  getch();


  

    /**********************************************************************************
                                                                                      *
                                  End of the main loop                                *
                                                                                      *
     **********************************************************************************/ 
 

  output_code(output,string_code);     /* Output the last code               */
  output_code(output,MAX_VALUE);       /* Output the end of buffer code      */
  output_code(output,0);               /* This code flushes the output buffer*/
  printf("\n");
}



/************************************************************************************************
**
**       This is the hashing routine.  It tries to find a match for the prefix+char
**       string in the string table.  If it finds it, the index is returned.  If
**       the string is not found, the first available index in the string table isreturned instead.
**        
*************************************************************************************************/



find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;

  index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
  if (index == 0)
    offset = 1;
  else
    offset = TABLE_SIZE - index;
  while (1)
  {
    if (code_value[index] == -1)
      return(index);
    if (prefix_code[index] == hash_prefix &&
	append_character[index] == hash_character)
      return(index);
    index -= offset;
    if (index < 0)
      index += TABLE_SIZE;
  }
}



/************************************************************************************************
*                                                                                               * 
*              The following two routines are used to output variable length codes.             *
*                                                                                               *
*                                                                                               *
************************************************************************************************/ 


input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;

  while (input_bit_count <= 24)
  {
    input_bit_buffer |=
	(unsigned long) getc(input) << (24-input_bit_count);
    input_bit_count += 8;
  }
  return_value=input_bit_buffer >> (32-BITS);
  input_bit_buffer <<= BITS;
  input_bit_count -= BITS;
  return(return_value);
}

output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;

  output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
  output_bit_count += BITS;
  while (output_bit_count >= 8)
  {
    putc(output_bit_buffer >> 24,output);
    output_bit_buffer <<= 8;
    output_bit_count -= 8;
  }
}

                               /************END**************/